/*
 * @lc app=leetcode.cn id=142 lang=golang
 *
 * [142] 环形链表 II
 */

// 2. 哈希
// @lc code=start
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
	m := map[*ListNode]int{}
	for head != nil {
		if _, ok := m[head]; ok {
			return head
		}
		m[head] = 1
		head = head.Next
	}
	return nil
}

// @lc code=end

// 1. 快慢指针
// 设 a = 环前节点数， b = 环的节点数
// 已知条件 fast = 2 * slow , fast - slow = nb
// 可得 slow = nb
// 又有条件 环的第一个节点 = a + nb
// 可知 slow 再走a步就是环的第一个节点
// 故可知head节点走a步 和slow走a步都会到环的第一个节点
// @lc code=start
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next

		if slow == fast {
			for head != slow {
				head = head.Next
				slow = slow.Next
			}
			return slow
		}
	}
	return nil
}

// @lc code=end

